class Solution {
    //动态规划：f(n) = f(i) * f(n - i)中的最大值
    //每剪一刀就会出现n-1种情况
public:
    int cuttingRope(int n) {
        if(n < 2)  return -1;

        int* sum = new int[n + 1];  //sum[n]对应的是长度为n的绳子所能分割的最大乘积
        for(int i = 0; i < n + 1; ++i)  sum[i] = 1;

        int max = 1;
        int halfOfI = 1;
        int store = 1;
        for(int i = 2; i <= n; ++i){
            max = sum[i];
            halfOfI = i /2;
            store = 1;
            //每个结点有两种情况：继续分割或停止分割,若分割后比分割前乘积要小，则不分割
            for(int j = 1; j <= halfOfI; ++j){
                store = (sum[j] > j ? sum[j] : j) * (sum[i - j] > i - j ? sum[i - j] : i - j);
                if(store > max)  max = store;
            }
            sum[i] = max;
        }

        int result = sum[n];
        delete[] sum;
        return result;
    }
};

class Solution {
    //贪心算法:当n>=5时，我们应尽可能把绳子剪成长度为3或2的绳子
public:
    int cuttingRope(int n) {
        if(n < 2)  return -1;
        if(2 == n)  return 1;
        if(3 == n)  return 2;

        int timesOf3 = n / 3;  //长为3的绳子段数
        int timesOf2 = 0;
        
        if((n - timesOf3*3) == 1){
            timesOf2 = 2;
            --timesOf3;
        }else if((n - timesOf3*3) == 2){
            timesOf2 = 1;
        }else{}

        return (int)(pow(3, timesOf3)) * (int)(pow(2, timesOf2));
    }
};